// @coding: utf8

/**
给定一个数组，包含0和非零，需要将所有的0移动到末尾，并且保证非0部分顺序不变。
 */


#include <iostream>
#include <vector>


std::vector<int> get_data()
{
    std::vector<int> vec{0,1,0,3,0,0,12, 0};
    return vec;
}

void dump_vector(std::vector<int>& vec)
{
    std::cout << "dump_vector:" << std::endl;
    for (auto item : vec)
    {
        std::cout << item << ",";
    }
    std::cout << std::endl;
}


// 原地移动值为0的数据到末尾，并且保持非0数据顺序不变
// left指针永远指向有效数据，right指针找到有效后马上交换给left然后left++。一趟循环完成，每个有效值都被放到了前面。
// @return: 返回的值指向有效值的下一个位置
int move_zero(std::vector<int>& vec)
{
    int left = 0;
    int right = 0;
    while (right < vec.size())
    {
        if (vec[right])
        {
            std::swap(vec[left], vec[right]);
            left++;
        }
        right++;
    }
    return left++;
}

int move_zero2(std::vector<int>& vec)
{
    int left = 0;
    int right = 0;
    while (right < vec.size())
    {
        // 找到有效结果，left增加
        if (vec[right] != 0)
        {
            if(left < right)
                vec[left] = vec[right];
            ++left;
        }
        ++right;
    }
    return left;
}

int main()
{
    auto data = get_data();
    dump_vector(data);
    move_zero(data);
    dump_vector(data);
    move_zero2(data);
    dump_vector(data);
    data = get_data();
    move_zero2(data);
    dump_vector(data);
    return 0;
}